#include <iostream>
#include <string>
using namespace std;

const int kMaxN = 5010;
const int kMod = 1e8;
int f[2][kMaxN];
int s[2][kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  string s1, s2;
  int n, m;

  cin >> s1 >> s2;

  n = s1.size() - 1;
  m = s2.size() - 1;
  s1 = "$" + s1;
  s2 = "$" + s2;
  for (int j = 0; j <= m; j++) {
    s[0][j] = 1;
  }
  for (int i = 1; i <= n; i++) {
    fill(f[i & 1], f[i & 1] + kMaxN, 0);
    fill(s[i & 1], s[i & 1] + kMaxN, 0);
    f[i & 1][0] = f[(i - 1) & 1][0];
    s[i & 1][0] = s[(i - 1) & 1][0];
    for (int j = 1; j <= m; j++) {
      f[i & 1][j] = max(f[(i - 1) & 1][j], f[i & 1][j - 1]);
      if (s1[i] == s2[j]) {
        f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - 1] + 1);
      }
      if (f[(i - 1) & 1][j] == f[i & 1][j]) {
        s[i & 1][j] += s[(i - 1) & 1][j];
      }
      if (f[i & 1][j - 1] == f[i & 1][j]) {
        s[i & 1][j] += s[i & 1][j - 1];
      }
      if (s1[i] != s2[j] && f[(i - 1) & 1][j - 1] == f[i & 1][j]) {
        s[i & 1][j] -= s[(i - 1) & 1][j - 1];
      }
      if (s1[i] == s2[j] && f[(i - 1) & 1][j - 1] + 1 == f[i & 1][j]) {
        s[i & 1][j] += s[(i - 1) & 1][j - 1];
      }
      (s[i & 1][j] += kMod) %= kMod;
    }
  }
  cout << f[n & 1][m] << "\n"
       << s[n & 1][m] << "\n";
  return 0;
}